package com.hcj.springcloud.tree;

/**
 * 二叉树的特性： 左子树永远小于右子树
 * 衍生出的算法：二分查找，它的时间复杂度为O long(n)
 * 特别一点的树：哈夫曼树，也叫最优二叉树（即，只有叶子节点才是有效的数据节点）,
 * 可以联想到“哈夫曼编码”： 出现频率低的在二叉树的左子树，出现频率高的在二叉树的右子树，只有叶子节点才是能用的数据
 */
public class BinaryTree implements Tree<Integer> {

    private Node<Integer> root;

    private Integer count = 0;

    /**
     * 其实就是一个二分查找（前提是有序的）
     *
     * @param data
     * @return
     * @remark 左边的值<右边的值
     */
    @Override
    public Node<Integer> find(Integer data) {
        Node<Integer> current = root;
        while ((current != null)) {
            if (data < current.getData()) {
                current = current.getLeft();
            } else if (data > current.getData()) {
                current = current.getRight();
            } else {
                return current;
            }
        }
        return null;
    }

    @Override
    public Boolean insert(Integer data) {
        Node<Integer> newNode = new Node<Integer>(data);
        if (root == null) {
            // 当前树为空，无任何节点
            root = newNode;
            return true;
        } else {
            Node<Integer> current = root;
            Node<Integer> parentNode = null;
            while (current != null) {
                parentNode = current;
                if (data < current.getData()) {
                    // 数据小于当前节点的数据，就把当前节点的左子树，作为新的父节点
                    current = current.getLeft();
                    if (current == null) {
                        // 如果左子树为空，则把数据插入到父节点的左子树中
                        parentNode.setLeft(newNode);
                        return true;
                    }
                } else {
                    current = current.getRight();
                    if (current == null) {
                        parentNode.setRight(newNode);
                        return true;
                    }
                }
            }
        }
        return false;
    }

    @Override
    public Boolean delete(Integer data) {
        Node<Integer> current = root;
        Node<Integer> parent = root;
        boolean isLeftChild = false;
        // 1.查找删除的节点, 如果未找到，则删除失败
        while (current.getData() != data) {
            parent = current;
            if (data < current.getData()) {
                isLeftChild = true;
                current = current.getLeft();
            } else {
                isLeftChild = false;
                current = current.getRight();
            }
            if (current == null) {
                return false;
            }
        }


        // 2.1如果当前节点没有子节点
        if (current.getLeft() == null && current.getRight() == null) {
            if (current == root) {
                root = null;
            } else if (isLeftChild) {
                parent.setLeft(null);
            } else {
                parent.setRight(null);
            }
            return true;
        }

        // 2.2.1如果当前节点有一个子节点(右节点)
        else if (current.getLeft() == null && current.getRight() != null) {
            if (current == root) {
                root = current.getRight();
            } else if (isLeftChild) {
                //
                parent.setLeft(current.getRight());
            } else {
                parent.setRight(current.getRight());
            }
            return true;
        }
        // 2.2.2如果当前节点有一个子节点(左节点)
        else if (current.getLeft() != null && current.getRight() == null) {
            if (current == root) {
                root = current.getLeft();
            } else if (isLeftChild) {
                parent.setLeft(current.getLeft());
            } else {
                parent.setRight(current.getLeft());
            }
            return true;
        }

        // 2.3如果当前节点有两个子节点【要触发重排- 中序排序的后继节点代替当前节点】
        else if (current.getLeft() != null && current.getRight() != null) {
            Node<Integer> successor = getSuccessorAndDelNode(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.setLeft(successor);
            } else {
                parent.setRight(successor);
            }
            successor.setLeft(current.getLeft());
            return true;
        }
        return false;
    }

    /**
     * 查找二叉树中最大值的节点
     *
     * @remark 即，遍历右子树的最后一个叶子节点
     */
    @Override
    public Node<Integer> findMax() {
        Node<Integer> current = root;
        Node<Integer> maxNode = current;
        while (current != null) {
            maxNode = current;
            current = current.getRight();
        }
        return maxNode;
    }

    /**
     * 查找二叉树中最小值的节点
     *
     * @remark 即，遍历左子树的最后一个叶子节点
     */
    @Override
    public Node<Integer> findMin() {
        Node<Integer> current = root;
        Node<Integer> minNode = current;
        while (current != null) {
            minNode = current;
            current = current.getLeft();
        }
        return minNode;
    }

    @Override
    public void preOrder(Node<Integer> root) {
        if (root != null) {
            System.out.print(root.getData() + " -> ");
            preOrder(root.getLeft());
            preOrder(root.getRight());
        }
    }

    @Override
    public void infixOrder(Node<Integer> root) {
        if (root != null) {
            infixOrder(root.getLeft());
            System.out.print(root.getData() + " -> ");
            infixOrder(root.getRight());
        }
    }

    /**
     * 第K小的节点：
     */
    public void infixOrder(Node<Integer> root, Integer k) {
        if (root != null) {
            infixOrder(root.getLeft(), k);
            count++;
            if (k == count) {
                System.err.print("第" + k + "小的节点为" + root.getData() + " -> ");
            } else {
                System.out.print(root.getData() + " -> ");
            }
            infixOrder(root.getRight(), k);
        }
    }

    @Override
    public void postOrder(Node<Integer> root) {
        if (root != null) {
            preOrder(root.getLeft());
            preOrder(root.getRight());
            System.out.print(root.getData() + " -> ");
        }
    }

    /**
     * 获取后继节点(比删除节点大的最小节点。)，并替换删除节点
     *
     * @param delNode
     * @return
     */
    private Node<Integer> getSuccessorAndDelNode(Node<Integer> delNode) {
        Node<Integer> successorParent = delNode;
        Node<Integer> successor = delNode;
        Node<Integer> current = delNode.getRight();
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.getLeft();
        }
        // 将后继节点替换为 删除节点
        if (successor != delNode.getRight()) {
            successorParent.setLeft(successor.getRight());
            successor.setRight(delNode.getRight());
        }
        return successor;
    }


    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.insert(50);// 会变成root值
        binaryTree.insert(20);
        binaryTree.insert(80);
        binaryTree.insert(10);
        binaryTree.insert(30);
        binaryTree.insert(60);
        binaryTree.insert(90);
        binaryTree.insert(25);
        binaryTree.insert(85);
        binaryTree.insert(100);
        /**
         * root的形状
         * <pre>
         *          50
         *         /  \
         *      20     80
         *     /  \    / \
         *   10   30  60  90
         *        /      /  \
         *       25     85   100
         * </pre>
         */
        System.out.println("最大值:    " + binaryTree.findMax().getData());
        System.out.println("最小值:    " + binaryTree.findMin().getData());
        System.out.println("查找110:  " + binaryTree.find(110));
        System.out.println("查找100:  " + binaryTree.find(100).getData());
        binaryTree.find(100).toJSON();
        System.out.println("查找50");
        binaryTree.find(50).toJSON();

        System.out.println("infixOrder:中序遍历开始");
        binaryTree.infixOrder(binaryTree.root);
        System.out.println("\ninfixOrder:中序遍历结束");
        System.out.println("preOrder:前序遍历开始");
        binaryTree.preOrder(binaryTree.root);
        System.out.println("\npreOrder:前序遍历结束");
        System.out.println("postOrder:后序遍历开始");
        binaryTree.postOrder(binaryTree.root);
        System.out.println("\npostOrder:后序遍历结束");


        binaryTree.delete(20);
        System.out.println("删除20后，整颗树变成：");
        binaryTree.root.toJSON();
        binaryTree.insert(20);
        binaryTree.delete(80);
        System.out.println("删除80后，整颗树变成：");
        binaryTree.root.toJSON();

        // 查找第K小的节点
        binaryTree.infixOrder(binaryTree.root, 3);

        /** 运行结果
         最大值:    100
         最小值:    10
         查找110:  null
         查找100:  100
         {"data":100}
         查找50
         {"data":50,"left":{"data":20,"left":{"data":10},"right":{"data":30,"left":{"data":25}}},"right":{"data":80,"left":{"data":60},"right":{"data":90,"left":{"data":85},"right":{"data":100}}}}
         infixOrder:中序遍历开始
         10 -> 20 -> 25 -> 30 -> 50 -> 60 -> 80 -> 85 -> 90 -> 100 ->
         infixOrder:中序遍历结束
         preOrder:前序遍历开始
         50 -> 20 -> 10 -> 30 -> 25 -> 80 -> 60 -> 90 -> 85 -> 100 ->
         preOrder:前序遍历结束
         postOrder:后序遍历开始
         20 -> 10 -> 30 -> 25 -> 80 -> 60 -> 90 -> 85 -> 100 -> 50 ->
         postOrder:后序遍历结束
         删除20后，整颗树变成：
         {"data":50,"left":{"data":25,"left":{"data":10},"right":{"data":30}},"right":{"data":80,"left":{"data":60},"right":{"data":90,"left":{"data":85},"right":{"data":100}}}}
         删除80后，整颗树变成：
         {"data":50,"left":{"data":25,"left":{"data":10,"right":{"data":20}},"right":{"data":30}},"right":{"data":85,"left":{"data":60},"right":{"data":90,"right":{"data":100}}}}
         */
    }


}
